﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace ShapeConnectors
{
    class Kruskal:CANHNA
    {
        public static List<BuocThucHien> BuocKruskal;
        string chuoi = null;
        List<int> nhankrus = new List<int>();        
        List<CANHNA> T = new List<CANHNA>();
        private int nT;
        List<int> labelkrus = new List<int>();
        List<CANHNA> Edge = new List<CANHNA>();
	    private int nE;
        public void ViSit(int i, int lb)
        {
            nhankrus[i] = lb;
            for (int j = 0; j < spt; j++)
            {
                if (nhankrus[j] == 0 && (a[i, j] > 0))
                {
                    ViSit(j, lb);
                }
            }
        }
        public int KTLT()
        {
            int lb = 0;
            for (int i = 0; i < spt; i++)
                nhankrus.Add(0);
            for (int i = 0; i < spt; i++)
            {
                if (nhankrus[i] == 0)
                {
                    lb++;
                    ViSit(i, lb);
                }
            }
            if (lb == 1)
                return 1;
            return 0;
        }
        public string XuatKruskal()
        {
            //int kq=KruskalAlg();
            int kt = KTLT();
            int temp = 0;
            if (kt == 1)
            {
                chuoi = "Cây tối đại ngắn nhất: ";
                for (int i = 0; i < nT; i++)
                {
                    chuoi +="\r\nCạnh"+ (T[i].GetDinh1()).ToString()+ "->" + (T[i].GetDinh2()).ToString() + ":" + T[i].GetTS().ToString()+"\n";
                    temp += T[i].GetTS();
                }
                chuoi = chuoi + "\r\n Trọng số :" + temp.ToString();
            }
            else
                chuoi = "Đồ thị không liên thông";
            return chuoi;
        }
        public void KhoiTaoKruskal()
        {
            int k=0;
	        for(int i=0;i<spt;i++)
	        {
                for (int j = i + 1; j < spt; j++)
                {
                    if (a[i, j] != 0)
                    {
                        CANHNA r = new CANHNA();
                        r.SetDinh1(i);
                        r.SetDinh2(j);
                        r.SetTS(a[i, j]);
                        Edge.Add(r);
                        k++;
                    }
                }
	        }
	        nE=k;
            for (int i = 0; i < spt; i++)
                labelkrus.Add(i);
	        SapTang();
        }
        public void SapTang()
        {
            for (int i = 0; i < nE - 1; i++)
            {
                for (int j = i + 1; j < nE; j++)
                {
                    if (Edge[i].GetTS() >= Edge[j].GetTS())
                    {
                        CANHNA temp = new CANHNA();
                        temp = Edge[i];
                        Edge[i] = Edge[j];
                        Edge[j] = temp;
                    }
                }
            }
        }
        public void UpdateLabel( int v1,int v2)
        {
            int min = labelkrus[v1];
            int max = labelkrus[v2];
            if (min >= max)
            {
                max = labelkrus[v1];
                min = labelkrus[v2];
            }
	        for(int i=0;i<spt;i++)
		        if(labelkrus[i]==max)
			        labelkrus[i]=min;
        }
        public int KruskalAlg()
        {
            BuocKruskal = new List<BuocThucHien>();
	        nT=0;
	        KhoiTaoKruskal();
	        for(int i=0;i<nE;i++)
	        {
                BuocThucHien buoc = new BuocThucHien();//
                buoc.KhoiTao();//khởi tạo các đối tượng của 1 bước//
                CANHNA Ed = new CANHNA();
                Ed=Edge[i];
		        int v1=Ed.GetDinh1();
		        int v2=Ed.GetDinh2();
                
                if (labelkrus[v1] != labelkrus[v2] )
		        {
                    buoc.Canhcanto = Ed; 
                    buoc.Dinhdau = Ed.GetDinh1();
                    buoc.Dinhcuoi = Ed.GetDinh2();
                    BuocKruskal.Add(buoc);
                    T.Add(Ed);
                    for (int b = 0; b < T.Count; b++)
                    {
                        buoc.Kqkruskal.Add(T[b]);
                    }
                    nT++;
			        UpdateLabel(v1,v2);
                    
		        }

                //if (l1 == l2)
                //    break;
		        if(nT==(spt-1))
			        break;
	        }
            if (nT == (spt - 1))
                return 1;
            return 0;

        }
    }
}
